package recursion;

import java.util.Arrays;

// 八皇后问题求解

public class Queue8 {
	// 皇后的个数
	int max = 8;
	// 摆放方案的个数
	static int count = 0;
	// 保存每个皇后的位置，因为每行只放一个皇后，所以只用了一个一维数组保存列号即可
	int[] arr = new int[max];
	
	public static void main(String[] args) {
		
		Queue8 queue8 = new Queue8();
		queue8.layout(0);
		System.out.println("八皇后问题共有"+count+"个解法");
	}
	
	// 放置皇后
	private void layout(int n) {
		if(n == max) {
			// 这时说明已经摆放完了
			System.out.println(Arrays.toString(arr));
			count++;
			return;
		}
		
		// 对每个皇后，都依次去尝试摆放在每一列
		for(int i = 0; i < max; i++) {
			arr[n] = i;
			// 判断这个皇后摆放位置是否冲突
			if(judge(n)) {
				// 如果当前位置不冲突，继续递归，摆放下一个皇后
				layout(n+1);
			}
			// 如果发生冲突，进入下一轮循环，尝试摆放在下一列
		}
	}
	
	// 判断第n个皇后是否和前面的冲突
	private boolean judge(int n) {
		for(int i = 0; i < n; i++) {
			// 判断是否在同一列，或一条对角线上
			if(arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[i] - arr[n])) {
				return false;
			}
		}
		return true;
	}
}